package org.example.myleet.inplace;

import org.example.myleet.Utils.ArrayUtils;
import org.example.myleet.Utils.ListNode;

/**
 * 原地算法
 */
public class InPlaceSolution {

    //面试题 17.19. 消失的两个数字
    public int[] missingTwo(int[] nums) {
        int N = nums.length + 2;
        int n_1 = -1;
        int n = -1;
        int j_1;
        for (int i = 0; i < nums.length; ++i) {
            //找到nums[i]数字应该放置的下标j-1
            j_1 = nums[i] - 1;
            while (j_1 >= 0 && j_1 != i) {
                if (j_1 < nums.length) {
                    //交换nums[i]和nums[j-1]的值，让nums[j-1]的值排正确
                    //虽然在while循环里，但这个操作最多只会做一次，类似于在链表上前进
                    nums[i] = nums[j_1];
                    nums[j_1] = j_1 + 1;
                } else if (j_1 == nums.length) {
                    //缺N-1
                    nums[i] = n_1;
                    n_1 = j_1 + 1;
                } else {
                    //缺N
                    nums[i] = n;
                    n = j_1 + 1;
                }
                j_1 = nums[i] - 1;
            }
        }
        int[] res = new int[2];
        int j = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == -1) {
                res[j++] = i + 1;
            }
        }
        if (j < 2) {
            if (n_1 == -1) {
                res[j++] = N - 1;
            }
            if (n == -1) {
                res[j] = N;
            }
        }
        return res;
    }

    //41. 缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        int n = nums.length, t, t_;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == Integer.MAX_VALUE) {
                //使每个数字都小于Integer.MAX_VALUE，方便后面打标记
                --nums[i];
            }
        }
        for (int i = 0; i < n; ++i) {
            if (0 < nums[i] && nums[i] <= n) {
                //若nums[i]的值不超过数组的长度，则开始探索比nums[i]小的数
                //取 t=nums[i]-1 作为下标
                t = nums[i] - 1;
                while (0 <= t && t < n) {
                    //当 t 值一直不超过数组的长度，则一直继续往小的数字探索
                    t_ = nums[t];
                    //t_为临时值。然后nums[t]被标记为Integer.MAX_VALUE，代表已经访问过了
                    nums[t] = Integer.MAX_VALUE;
                    //更新下一个需要访问的数组下标
                    t = t_ - 1;
                }
            }
        }
        //经过以上O(n)复杂度的遍历之后，数组中没有被标记为Integer.MAX_VALUE的第一个位置的下标（按从1开始计）就是未出现的最小正整数
        for (int i = 0; i < n; ++i) {
            if (nums[i] < Integer.MAX_VALUE) {
                return i + 1;
            }
        }
        //这里代表整个数组全被标记为Integer.MAX_VALUE了，代表从1~n都在数组中出现了，所以未出现的最小正整数就是n+1
        return n + 1;
    }

    /**
     * 73【原地算法】矩阵置零
     * 1 ms
     * 思考：某个位置[i,j]为0时，行、列均置为0，可以表示成第i行为0，第j行为0，利用matrix[i][0]和matrix[0][j]记录需要置为0的行和列，
     * 注意因为第一行和第一列被用作标记，所以左上角的第一行和第一列比较特殊，需要最后再特殊处理
     * 使用第一列和第一行作为需要置0的标记
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        //a - 第一列是否有0；b - 第一行是否有0
        boolean a = false, b = false;
        for (int i=0; i<m; ++i) {
            if (matrix[i][0] == 0) {
                a = true;
                break;
            }
        }
        for (int j=0; j<n; ++j) {
            if (matrix[0][j] == 0) {
                b = true;
                break;
            }
        }
        //遍历矩阵打标记，利用matrix[i][0]和matrix[0][j]记录需要置为0的行和列
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        //除第一行和第一列以外，全部被标记打行和列置为0
        for (int i=1; i<m; ++i) {
            if (matrix[i][0] == 0) {
                for (int j=0; j<n; ++j) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j=1; j<n; ++j) {
            if (matrix[0][j] == 0) {
                for (int i=0; i<m; ++i) {
                    matrix[i][j] = 0;
                }
            }
        }
        //最后处理第一行和第一列的情况
        if (a) {
            for (int i=0; i<m; ++i) {
                matrix[i][0] = 0;
            }
        }
        if (b) {
            for (int j=0; j<n; ++j) {
                matrix[0][j] = 0;
            }
        }
    }

    /**
     * 80【双指针 + 原地算法】删除有序数组中的重复项 II
     * 1 ms
     * 双指针 + 原地算法
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) {
            //长度小于3的情况不可能存在需要去重的情况
            return nums.length;
        }
        //第一个指针是size，代表数组当前有效的长度；第二个指针是cur，代表当前扫描到的位置；repeat记录的是当前出现重复的值
        int size = 1, cur = 1, repeat = Integer.MIN_VALUE;
        while (cur < nums.length) {
            if (nums[cur] == nums[cur-1]) {
                //当前值与上一个值相同
                if (nums[cur] != repeat) {
                    //刷新repeat的值，并将数值移到当前位置，两个指针都向前移动
                    repeat = nums[cur];
                    nums[size++] = nums[cur++];
                } else {
                    //超过两个相同值，则这个位置的值被丢弃
                    ++cur;
                }
            } else {
                //当前值与上一个值不同，将数值移到当前位置，两个指针都向前移动
                nums[size++] = nums[cur++];
            }
        }
        return size;
    }

    //88. 合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int e1 = m - 1, e2 = n - 1, p = nums1.length - 1;
        while (e1 >= 0 && e2 >= 0) {
            if (nums1[e1] >= nums2[e2]) {
                nums1[p] = nums1[e1];
                --e1;
            } else {
                nums1[p] = nums2[e2];
                --e2;
            }
            --p;
        }
        while (e1 >= 0) {
            nums1[p] = nums1[e1];
            --e1;
            --p;
        }
        while (e2 >= 0) {
            nums1[p] = nums2[e2];
            --e2;
            --p;
        }
    }

    /**
     * 189【翻转数组法（原地算法）】轮转数组
     * 翻转k次数组，事实上就是将数组前k个数字放到数组结尾，因此通过一次1~n的翻转将前k个数字翻到数组尾部
     * 再通过1~k、k+1~n两个范围内的数字翻转恢复原来的顺序
     */
    public void rotate(int[] nums, int k) {
        if (k >= nums.length) {
            k = k % nums.length;
        }
        ArrayUtils.reverse(nums, 0, nums.length-1);
        ArrayUtils.reverse(nums, 0, k-1);
        ArrayUtils.reverse(nums, k, nums.length-1);
    }

    /**
     * 237【原地算法】删除链表中的节点
     * 官方解：投机取巧，原地算法，下一个节点的值放到这个节点之后，删除下一个节点即可
     */
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * 268【原地算法】丢失的数字
     * 在原数组中通过交换数值对数值归位
     */
    public int missingNumber(int[] nums) {
        //将nums[idx]视作第i个数（i从1开始数），其下标为nums[idx] - 1
        //idx为遍历到的游标位置，nextIdx为nums[idx] - 1，zeroIdx为0值所在的下标，如果0一直找不到，就会保持-1
        int idx = 0, nextIdx, zeroIdx = -1;
        while (idx < nums.length) {
            if (nums[idx] != 0) {
                //nums[idx]的值不为0，则将其下标对应位置的值和这个值交换，交换之后即完成一个位置的正确排序
                //一直重复这个步骤，直到idx位置上的值对应其下标
                nextIdx = nums[idx] - 1;
                while (idx != nextIdx && nextIdx > -1) {
                    int t = nums[nextIdx];
                    nums[nextIdx] = nums[idx];
                    nums[idx] = t;
                    nextIdx = nums[idx] - 1;
                    if (nums[idx] == 0) {
                        //发现0值，更新0的位置下标
                        zeroIdx = idx;
                    }
                }
            } else {
                //发现0值，更新0的位置下标
                zeroIdx = idx;
            }
            //遍历游标前进
            ++idx;
        }
        //zeroIdx代表缺失的数的下标，+1就是对应的数
        return zeroIdx + 1;
    }

    /**
     * 283【原地算法】移动零
     * 0 ms
     * 这个办法少了往复循环查询的情况，最坏复杂度O(n+n) = O(2n)
     */
    public void moveZeroes(int[] nums) {
        int nonZeroCount = 0, len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                //找到非0的数，叠到左边，左边的下一个放置非0数的位置前进一位
                nums[nonZeroCount] = nums[i];
                if (i != nonZeroCount) {
                    //相当于交换好非0位置的数，0被换到靠尾的地方了
                    nums[i] = 0;
                }
                ++nonZeroCount;
            }
        }
    }

    /**
     * 328【原地算法】奇偶链表
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //偶数位置列的头节点，当前偶数位置列的节点，当前遍历节点，当前节点的上一个节点（其实永远都是奇数位置的节点）
        ListNode evenHead = null, curEvenNode = null, curNode = head, lastNode = null;
        int i=1;
        while (true) {
            if ((i&1) == 0) {
                //偶数位置
                if (evenHead == null) {
                    //偶数位置列初始化
                    evenHead = curNode;
                    curEvenNode = evenHead;
                } else {
                    //偶数位置列节点保存当前偶数位置节点
                    curEvenNode.next = curNode;
                    curEvenNode = curEvenNode.next;
                }
                //上一个节点（奇数位置节点）连接到下一个奇数节点
                lastNode.next = curNode.next;
            }
            if (curNode.next == null) {
                //到链尾了，要退出了，这时需要做一个特殊处理
                if (curEvenNode.next != null) {
                    //这种情况的出现是因为数列长度是奇数，因此偶数位置列的最后一个是奇数（没处理到），需要从偶数位置列中抹掉
                    curEvenNode.next = null;
                } else {
                    //这种情况出现的原因是数列长度是偶数，当前节点停在了偶数位置，但是最后需要将奇数位置数列和偶数位置数列缝合
                    //缝合位置必须是在奇数位置数列的尾巴上，因此将当前节点退一位
                    curNode = lastNode;
                }
                break;
            }
            //游标、上一个节点、当前节点前进一位
            ++i;
            lastNode = curNode;
            curNode = curNode.next;
        }
        //最后做缝合操作，当前节点代表奇数位置数列的尾巴，连接到偶数数列的头部，完成
        curNode.next = evenHead;
        return head;
    }
}
